use std::{mem::swap, usize};
use std::fmt::Debug;

#[derive(Debug)]
pub struct Heap<T> {
    arr: Vec<T>,
    size: usize, // heap size
    heap_type: HeapType,
}

#[derive(Debug)]
pub enum HeapType {
    BIG,
    SMALL,
}

impl <T:Sized+Ord+PartialEq + Copy + Debug > Heap<T> {
    pub fn big(size:usize) -> Self {
        Self{
            arr: vec![],
            size,
            heap_type:HeapType::BIG
        }
    }


    pub fn small(size: usize) -> Self {
        Self {
            arr: vec![],
            size,
            heap_type:HeapType::SMALL
        }
    }

    pub fn output(&self)  {
        println!("heap data: {:#?}", self.heap_type);
        for (i,v) in self.arr.iter().enumerate() {
            print!( "{:?}", &v);
            if i != self.arr.len() - 1 {
                print!(" => ");
            } else {
                println!("\n\n")
            }
        }
    }

    pub fn build_heap_from_slice(&mut self, data:&[T]) {
        if data.len() == 0 {
            return;
        }
        let min = self.size.min(data.len());
        self.arr.reserve(self.size);
        self.arr.push(data[0].clone());
        for i in 1..min {
            self.arr.push(data[i].clone());
            self.heapify_down_up(i)
        }

        if data.len() > self.size {
            for i in min + 1 ..data.len() {
                self.insert_heap(data[i].clone())
            }
        }
    }

    fn insert_heap(&mut self, mut data: T) {
        match self.heap_type {
            HeapType::BIG => {
                let mut i = self.size - 1;
                while data > self.arr[i] {
                    let temp = self.arr[i];
                    self.arr[i] = data;
                    data = temp;
                    if i == 0 { break; }
                    i /= 2;
                }
            },
            HeapType::SMALL => {
                let mut i = self.size - 1;
                while data < self.arr[i] {
                    let temp = self.arr[i];
                    self.arr[i] = data;
                    data = temp;
                    if i == 0 { break; }
                    i /= 2;
                }
            }
        }
    }   

    fn heapify_down_up(&mut self, mut idx: usize) {
        let mut parent_idx = (idx - 1) / 2;
        match self.heap_type {
            HeapType::BIG => {
                while self.arr[idx] > self.arr[parent_idx] {
                    self.arr.swap(idx, parent_idx);
                    idx = parent_idx;
                    if idx == 0 { break;}
                    parent_idx = ( idx - 1) /2;
                }
            },
            HeapType::SMALL => {
                while self.arr[idx] < self.arr[parent_idx] {
                    self.arr.swap(idx, parent_idx);
                    idx = parent_idx;
                    if idx == 0 { break;}
                    parent_idx = ( idx - 1) /2;
                }
            }
        }
        
    }

    fn heapify_up_down(&mut self, mut idx: usize) {
        loop {

        }
    }
}


#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn heap_test() {
        let mut h = Heap::<i32>::big(5);
        let n = [3,5,2,9,6,8,1];
        h.build_heap_from_slice(&n);
        h.output();
    }
}